#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

//test on 1337 online judge and pass all the test
class Solution1 {
    public:
        int jump(int A[], int n) {
            int jump = 0;
            int i = 0;
            int count = 0;
            while (i < n-1 && count < 200) {
                int move = 0;
                int max = 0;
                for (int j = i+1; j <= i + A[i]; j++) {
					if (j >= n-1) return jump+1;
                    if (j + A[j] > max) {
                        max = j + A[j];
                        move = j;
                    }
	//				cout << move << endl;
                }
                jump++;
                i = move;
                count++;
            }
            return jump;
        }
};

class Solution {
public:
    int jump(int A[], int n) {
        int cnt = 0 ; 
        int cur = 0;
        if (n == 1) 
            return 0;
        while (cur < n-1) {
            int prev = cur;
            int next = cur;
            int maxStep = 0;
            if (cur + A[cur] >= n-1) return cnt +1;
            for (int i = cur+1; i <= cur + A[cur] ;i++) {
                if (maxStep < i + A[i]) {
                    maxStep = i + A[i];
                    next = i;
                }   
             }   
            cnt++;
            cur = next;
        }   
        return cnt;
    }   
};

int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    int test[] = {2,3,1};
    int result = mySolution.jump(test, sizeof(test)/sizeof(int));
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
